class Solution {
public:
    TreeNode* Build(vector<int>& preorder, vector<int>& inorder, int& previ,
                    int begin, int end) {
        if (begin > end)
            return nullptr;
        // 根据前序确定根
        TreeNode* root = new TreeNode(preorder[previ]);
        // 通过中序和根划分区间
        int rooti = begin;
        while (rooti<end&&inorder[rooti] != root->val) {
                rooti++;
        }
        // [begin,rooti-1]rooti[rooti+1,end]
        previ++;
        root->left = Build(preorder, inorder, previ, begin, rooti - 1);
        root->right = Build(preorder, inorder, previ, rooti + 1, end);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int prev = 0;
        return Build(preorder, inorder, prev, 0, inorder.size() - 1);
    }
};